package com.buddy.summary.code.algorithm;

import java.util.Arrays;

public class CountSort {
    private static int[] countSort(int[] arr) {
        //1.得到数组的最大值
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        //2.根据数组最大值，确定统计数组的长度
        int[] countArr = new int[max + 1];
        //3.遍历数组，填充统计数组
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        //遍历统计数组，输出结果
        int index = 0;
        int[] sortedArr = new int[arr.length];
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                sortedArr[index++] = i;
            }
        }
        return sortedArr;
    }

    private static int[] countSort2(int[] arr) {
        //1.得到数组最大和最小值，并计算差值
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        int d = max - min + 1;
        //2.创建统计数组，并统计对应元素的个数
        int[] countArr = new int[d];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - min]++;
        }
        System.out.println(Arrays.toString(countArr));
        //3.统计数组变形,后面的元素等于前面的元素的和
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i - 1];
        }
        System.out.println(Arrays.toString(countArr));
        //4.倒序遍历原始数组,从统计数组中找到正确位置,输出到结果数组
        int[] sortedArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArr[countArr[arr[i]-min] - 1] = arr[i];
            countArr[arr[i]-min]--;
        }
        return sortedArr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10};
        int[] sortedArr = countSort(arr);
        System.out.println(Arrays.toString(sortedArr));

        int[] arr2 = new int[]{95,94,91,98,99,90,99,93,91,92};
        int[] sortedArr2 = countSort2(arr2);
        System.out.println(Arrays.toString(sortedArr2));
    }
}
